﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
//using System.Diagnostics.Stopwatch;

namespace minichess
{

    public static class GlobalMoveData
    {
        public static string[] valid_white_moves = new string[1000];
        public static int num_valid_white_moves = 0;
        public static string[] valid_black_moves = new string[1000];
        public static int num_valid_black_moves = 0;
        public static string best_move = "";
        public static bool DEBUG = false;
    };

    class Program
    {
        public static string board = "kqbnrppppp..........PPPPPRNBQK";
        //public static string board = "......k....p....Q...........K.";
        public static string turn = "W";
        static void Main(string[] args)
        {
            print_board(board);

            int move_count = 1;

            //Console.WriteLine("game over: {0}", game_over(board, move_count));

            while (game_over(board,move_count)==0)
            {
                // load valid moves for player's turn and select the best move to make
                if(turn=="W")
	            {
                    get_valid_white_moves(board);
		            //board = get_best_white_move();
                    board = best_negamax_move(board, 1, 1000);
                    Array.Clear(GlobalMoveData.valid_white_moves,0,GlobalMoveData.num_valid_white_moves);
                    GlobalMoveData.num_valid_white_moves = 0;
		            turn = "B";
	            }
	            else
	            {
                    get_valid_black_moves(board);
		            //board = get_best_black_move();
                    board = best_negamax_move(board, -1, 1000);
                    Array.Clear(GlobalMoveData.valid_black_moves, 0, GlobalMoveData.num_valid_black_moves);
                    GlobalMoveData.num_valid_black_moves = 0;
		            turn = "W";
	            }

                Console.WriteLine("Move {0}", move_count);
                print_board(board);

                if(game_over(board,move_count)!=0)
	            {
		            Console.WriteLine("Game over!!");
                    if (game_over(board,move_count) == 1)
                        Console.WriteLine("Black wins");
                    else if (game_over(board, move_count) == 2)
                        Console.WriteLine("White wins");
                    else
                        Console.WriteLine("Tie");
		            break;
	            }

                /*
                // get input from user for moves
                Console.WriteLine("Enter input:"); // Prompt
                string line = Console.ReadLine(); // Get string from user
                if (line == "exit") // Check string
                {
                    break;
                }
                
                Console.WriteLine("You typed "); // Report output
                Console.Write(line.Length);
                Console.WriteLine(" character(s)");
                */

                move_count++;
            }

            if (move_count > 40)
            {
                // if game is not over, then it's a draw game
                Console.WriteLine("Game over: Draw");
            }

            
        }

        static void get_valid_white_moves(string board)
        {
	        for(int i=0;i<board.Length;i++)
	        {
		        switch(board[i])
		        {
			        case 'K': valid_white_king_moves(board,i); break;
			        case 'Q': valid_white_queen_moves(board,i); break;
			        case 'B': valid_white_bishop_moves(board,i); break;
			        case 'N': valid_white_knight_moves(board,i); break;
			        case 'R': valid_white_rook_moves(board,i); break;
			        case 'P': valid_white_pawn_moves(board,i); break;
		        }
	        }
        }

        static void get_valid_black_moves(string board)
        {
	        for(int i=0;i<board.Length;i++)
	        {
		        switch(board[i])
		        {
			        case 'k': valid_black_king_moves(board,i); break;
			        case 'q': valid_black_queen_moves(board,i); break;
			        case 'b': valid_black_bishop_moves(board,i); break;
			        case 'n': valid_black_knight_moves(board,i); break;
			        case 'r': valid_black_rook_moves(board,i); break;
			        case 'p': valid_black_pawn_moves(board,i); break;
		        }
	        }
        }

        static void valid_white_king_moves(string board, int pos)
        {
	        // check north
	        string n = whats_north(board, pos);
	        if(GlobalMoveData.DEBUG)   Console.WriteLine("n: {0}",n);
	        if(n!=null && (n=="." || ((int)n[0]) > 96))
		        GlobalMoveData.valid_white_moves[GlobalMoveData.num_valid_white_moves++] = move_north(board, pos);
	
	        // check west
	        string w = whats_west(board, pos);
	        if(GlobalMoveData.DEBUG)   Console.WriteLine("w: {0}",w);
	        if(w!=null && (w=="." || ((int)w[0]) > 96))
		        GlobalMoveData.valid_white_moves[GlobalMoveData.num_valid_white_moves++] = move_west(board, pos);

	        // check south
	        string s = whats_south(board, pos);
	        if(GlobalMoveData.DEBUG)   Console.WriteLine("s: {0}",s);
	        if(s!=null && (s=="." || ((int)s[0]) > 96))
		        GlobalMoveData.valid_white_moves[GlobalMoveData.num_valid_white_moves++] = move_south(board, pos);

	        // check east
	        string e = whats_east(board, pos);
	        if(GlobalMoveData.DEBUG)   Console.WriteLine("e: {0}",e);
	        if(e!=null && (e=="." || ((int)e[0]) > 96))
		        GlobalMoveData.valid_white_moves[GlobalMoveData.num_valid_white_moves++] = move_east(board, pos);
	
	        // check southeast
	        string se = whats_southeast(board, pos);
	        if(GlobalMoveData.DEBUG)   Console.WriteLine("se: {0}",se);
	        if(se!=null && (se=="." || ((int)se[0]) > 96))
		        GlobalMoveData.valid_white_moves[GlobalMoveData.num_valid_white_moves++] = move_southeast(board, pos);
	
	        // check southwest
	        string sw = whats_southwest(board, pos);
	        if(GlobalMoveData.DEBUG)   Console.WriteLine("sw: {0}",sw);
	        if(sw!=null && (sw=="." || ((int)sw[0]) > 96))
		        GlobalMoveData.valid_white_moves[GlobalMoveData.num_valid_white_moves++] = move_southwest(board, pos);
	
	        // check northwest
	        string nw = whats_northwest(board, pos);
	        if(GlobalMoveData.DEBUG)   Console.WriteLine("nw: {0}",nw);
	        if(nw!=null && (nw=="." || ((int)nw[0]) > 96))
		        GlobalMoveData.valid_white_moves[GlobalMoveData.num_valid_white_moves++] = move_northwest(board, pos);
	
	        // check northeast
	        string ne = whats_northeast(board, pos);
	        if(GlobalMoveData.DEBUG)   Console.WriteLine("ne: {0}",ne);
	        if(ne!=null && (ne=="." || ((int)ne[0]) > 96))
                GlobalMoveData.valid_white_moves[GlobalMoveData.num_valid_white_moves++] = move_northeast(board, pos);
        }

        static void valid_white_queen_moves(string board, int pos)
        {
	        string orig_board = board;
	        int orig_pos = pos;
	
	        // check north
	        while(true)
	        {
		        string n = whats_north(board, pos);
		        if(GlobalMoveData.DEBUG)   Console.WriteLine("n: {0}",n);
		        if(n!=null && (n=="." || ((int)n[0]) > 96))
		        {
			        board = move_north(board, pos);
                    GlobalMoveData.valid_white_moves[GlobalMoveData.num_valid_white_moves++] = board;
			        if(n!=".") break;
		        }
		        else
			        break;
		        pos -= 5;
	        }
	
	        // check west
	        board = orig_board;
	        pos = orig_pos;
	        while(true)
	        {
		        string w = whats_west(board, pos);
		        if(GlobalMoveData.DEBUG)   Console.WriteLine("w: {0}",w);
		        if(w!=null && (w=="." || ((int)w[0]) > 96))
		        {
			        board = move_west(board, pos);
			        GlobalMoveData.valid_white_moves[GlobalMoveData.num_valid_white_moves++] = board;
			        if(w!=".") break;
		        }
		        else
			        break;
		        pos--;
	        }
	
	
	        // check south
	        board = orig_board;
	        pos = orig_pos;
	        while(true)
	        {
		        string s = whats_south(board, pos);
		        if(GlobalMoveData.DEBUG)   Console.WriteLine("s: {0}",s);
		        if(s!=null && (s=="." || ((int)s[0]) > 96))
		        {
			        board = move_south(board, pos);
			        GlobalMoveData.valid_white_moves[GlobalMoveData.num_valid_white_moves++] = board;
			        if(s!=".") break;
		        }
		        else
			        break;
		        pos += 5;
	        }
	
	
	        // check east
	        board = orig_board;
	        pos = orig_pos;
	        while(true)
	        {
		        string e = whats_east(board, pos);
		        if(GlobalMoveData.DEBUG)   Console.WriteLine("e: {0}",e);
		        if(e!=null && (e=="." || ((int)e[0]) > 96))
		        {
			        board = move_east(board, pos);
			        GlobalMoveData.valid_white_moves[GlobalMoveData.num_valid_white_moves++] = board;
			        if(e!=".") break;
		        }
		        else
			        break;
		        pos++;
	        }
	
	
	        // check southeast
	        board = orig_board;
	        pos = orig_pos;
	        while(true)
	        {
		        string se = whats_southeast(board, pos);
		        if(GlobalMoveData.DEBUG)   Console.WriteLine("se: {0}",se);
		        if(se!=null && (se=="." || ((int)se[0]) > 96))
		        {
			        board = move_southeast(board, pos);
			        GlobalMoveData.valid_white_moves[GlobalMoveData.num_valid_white_moves++] = board;
			        if(se!=".") break;
		        }
		        else
			        break;
		        pos += 6;
	        }
	
	
	
	        // check southwest
	        board = orig_board;
	        pos = orig_pos;
	        while(true)
	        {
		        string sw = whats_southwest(board, pos);
		        if(GlobalMoveData.DEBUG)   Console.WriteLine("sw: {0}",sw);
		        if(sw!=null && (sw=="." || ((int)sw[0]) > 96))
		        {
			        board = move_southwest(board, pos);
			        GlobalMoveData.valid_white_moves[GlobalMoveData.num_valid_white_moves++] = board;
			        if(sw!=".") break;
		        }
		        else
			        break;
		        pos += 4;
	        }
	
	
	        // check northwest
	        board = orig_board;
	        pos = orig_pos;
	        while(true)
	        {
		        string nw = whats_northwest(board, pos);
		        if(GlobalMoveData.DEBUG)   Console.WriteLine("nw: {0}",nw);
		        if(nw!=null && (nw=="." || ((int)nw[0]) > 96))
		        {
			        board = move_northwest(board, pos);
			        GlobalMoveData.valid_white_moves[GlobalMoveData.num_valid_white_moves++] = board;
			        if(nw!=".") break;
		        }
		        else
			        break;
		        pos -= 6;	
	        }
	
	
	        // check northeast
	        board = orig_board;
	        pos = orig_pos;
	        while(true)
	        {
		        string ne = whats_northeast(board, pos);
		        if(GlobalMoveData.DEBUG)   Console.WriteLine("ne: {0}",ne);
		        if(ne!=null && (ne=="." || ((int)ne[0]) > 96))
		        {
			        board = move_northeast(board, pos);
			        GlobalMoveData.valid_white_moves[GlobalMoveData.num_valid_white_moves++] = board;
			        if(ne!=".") break;
		        }
		        else
			        break;
		        pos -= 4;
	        }
        }

        static void valid_white_rook_moves(string board, int pos)
        {
	        string orig_board = board;
	        int orig_pos = pos;
	
	        // check north
	        while(true)
	        {
		        string n = whats_north(board, pos);
		        if(GlobalMoveData.DEBUG)   Console.WriteLine("n: {0}",n);
		        if(n!=null && (n=="." || ((int)n[0]) > 96))
		        {
			        board = move_north(board, pos);
			        GlobalMoveData.valid_white_moves[GlobalMoveData.num_valid_white_moves++] = board;
			        if(n!=".") break;
		        }
		        else
			        break;
		        pos -= 5;
	        }
	
	        // check west
	        board = orig_board;
	        pos = orig_pos;
	        while(true)
	        {
		        string w = whats_west(board, pos);
		        if(GlobalMoveData.DEBUG)   Console.WriteLine("w: {0}",w);
		        if(w!=null && (w=="." || ((int)w[0]) > 96))
		        {
			        board = move_west(board, pos);
			        GlobalMoveData.valid_white_moves[GlobalMoveData.num_valid_white_moves++] = board;
			        if(w!=".") break;
		        }
		        else
			        break;
		        pos--;
	        }
	
	        // check south
	        board = orig_board;
	        pos = orig_pos;
	        while(true)
	        {
		        string s = whats_south(board, pos);
		        if(GlobalMoveData.DEBUG)   Console.WriteLine("s: {0}",s);
                if (s != null && (s == "." || ((int)s[0]) > 96))
		        {
			        board = move_south(board, pos);
			        GlobalMoveData.valid_white_moves[GlobalMoveData.num_valid_white_moves++] = board;
			        if(s!=".") break;
		        }
		        else
			        break;
		        pos += 5;
	        }
	
	        // check east
	        board = orig_board;
	        pos = orig_pos;
	        while(true)
	        {
		        string e = whats_east(board, pos);
		        if(GlobalMoveData.DEBUG)   Console.WriteLine("e: {0}",e);
                if (e != null && (e == "." || ((int)e[0]) > 96))
		        {
			        board = move_east(board, pos);
			        GlobalMoveData.valid_white_moves[GlobalMoveData.num_valid_white_moves++] = board;
			        if(e!=".") break;
		        }
		        else
			        break;
		        pos++;
	        }
        }

        static void valid_white_bishop_moves(string board, int pos)
        {
	        
	
	        string orig_board = board;
	        int orig_pos = pos;
	
	        // check north
	        string n = whats_north(board, pos);
	        if(GlobalMoveData.DEBUG)   Console.WriteLine("n: {0}",n);
	        if(n!=null && n==".")
		        GlobalMoveData.valid_white_moves[GlobalMoveData.num_valid_white_moves++] = move_north(board, pos);
	
	        // check west
	        string w = whats_west(board, pos);
	        if(GlobalMoveData.DEBUG)   Console.WriteLine("w: {0}",w);
	        if(w!=null && w==".")
		        GlobalMoveData.valid_white_moves[GlobalMoveData.num_valid_white_moves++] = move_west(board, pos);

	        // check south
	        string s = whats_south(board, pos);
	        if(GlobalMoveData.DEBUG)   Console.WriteLine("s: {0}",s);
	        if(s!=null && s==".")
		        GlobalMoveData.valid_white_moves[GlobalMoveData.num_valid_white_moves++] = move_south(board, pos);

	        // check east
	        string e = whats_east(board, pos);
	        if(GlobalMoveData.DEBUG)   Console.WriteLine("e: {0}",e);
	        if(e!=null && e==".")
                GlobalMoveData.valid_white_moves[GlobalMoveData.num_valid_white_moves++] = move_east(board, pos);
	
	        // check southeast
	        board = orig_board;
	        pos = orig_pos;
	        while(true)
	        {
		        string se = whats_southeast(board, pos);
		        if(GlobalMoveData.DEBUG)   Console.WriteLine("se: {0}",se);
		        if(se!=null && (se=="." || ((int)se[0]) > 96))
		        {
			        board = move_southeast(board, pos);
			        GlobalMoveData.valid_white_moves[GlobalMoveData.num_valid_white_moves++] = board;
			        if(se!=".") break;
		        }
		        else
			        break;
		        pos += 6;
	        }
	
	
	
	        // check southwest
	        board = orig_board;
	        pos = orig_pos;
	        while(true)
	        {
		        string sw = whats_southwest(board, pos);
		        if(GlobalMoveData.DEBUG)   Console.WriteLine("sw: {0}",sw);
		        if(sw!=null && (sw=="." || ((int)sw[0]) > 96))
		        {
			        board = move_southwest(board, pos);
			        GlobalMoveData.valid_white_moves[GlobalMoveData.num_valid_white_moves++] = board;
			        if(sw!=".") break;
		        }
		        else
			        break;
		        pos += 4;
	        }
	
	
	        // check northwest
	        board = orig_board;
	        pos = orig_pos;
	        while(true)
	        {
		        string nw = whats_northwest(board, pos);
		        if(GlobalMoveData.DEBUG)   Console.WriteLine("nw: {0}",nw);
		        if(nw!=null && (nw=="." || ((int)nw[0]) > 96))
		        {
			        board = move_northwest(board, pos);
			        GlobalMoveData.valid_white_moves[GlobalMoveData.num_valid_white_moves++] = board;
			        if(nw!=".") break;
		        }
		        else
			        break;
		        pos -= 6;	
	        }
	
	
	        // check northeast
	        board = orig_board;
	        pos = orig_pos;
	        while(true)
	        {
		        string ne = whats_northeast(board, pos);
		        if(GlobalMoveData.DEBUG)   Console.WriteLine("ne: {0}",ne);
		        if(ne!=null && (ne=="." || ((int)ne[0]) > 96))
		        {
			        board = move_northeast(board, pos);
			        GlobalMoveData.valid_white_moves[GlobalMoveData.num_valid_white_moves++] = board;
			        if(ne!=".") break;
		        }
		        else
			        break;
		        pos -= 4;
	        }
        }

        static void valid_white_knight_moves(string board, int pos)
        {
	        
	
	        // check northwest
	        string nw = whats_knight_northwest(board, pos);
	        if(GlobalMoveData.DEBUG)   Console.WriteLine("nw: {0}",nw);
	        if(nw!=null && (nw=="." || ((int)nw[0]) > 96))
		        GlobalMoveData.valid_white_moves[GlobalMoveData.num_valid_white_moves++] = move_knight_northwest(board, pos);
	
	        // check northeast
	        string ne = whats_knight_northeast(board, pos);
	        if(GlobalMoveData.DEBUG)   Console.WriteLine("ne: {0}",ne);
	        if(ne!=null && (ne=="." || ((int)ne[0]) > 96))
		        GlobalMoveData.valid_white_moves[GlobalMoveData.num_valid_white_moves++] = move_knight_northeast(board, pos);
		
	        // check eastnorth
	        string en = whats_knight_eastnorth(board, pos);
	        if(GlobalMoveData.DEBUG)   Console.WriteLine("en: {0}",en);
	        if(en!=null && (en=="." || ((int)en[0]) > 96))
		        GlobalMoveData.valid_white_moves[GlobalMoveData.num_valid_white_moves++] = move_knight_eastnorth(board, pos);
		
	        // check eastsouth
	        string es = whats_knight_eastsouth(board, pos);
	        if(GlobalMoveData.DEBUG)   Console.WriteLine("es: {0}",es);
	        if(es!=null && (es=="." || ((int)es[0]) > 96))
		        GlobalMoveData.valid_white_moves[GlobalMoveData.num_valid_white_moves++] = move_knight_eastsouth(board, pos);
		
	        // check southeast
	        string se = whats_knight_southeast(board, pos);
	        if(GlobalMoveData.DEBUG)   Console.WriteLine("se: {0}",se);
	        if(se!=null && (se=="." || ((int)se[0]) > 96))
		        GlobalMoveData.valid_white_moves[GlobalMoveData.num_valid_white_moves++] = move_knight_southeast(board, pos);
		
	        // check southwest
	        string sw = whats_knight_southwest(board, pos);
	        if(GlobalMoveData.DEBUG)   Console.WriteLine("sw: {0}",sw);
	        if(sw!=null && (sw=="." || ((int)sw[0]) > 96))
		        GlobalMoveData.valid_white_moves[GlobalMoveData.num_valid_white_moves++] = move_knight_southwest(board, pos);
		
	        // check westsouth
	        string ws = whats_knight_westsouth(board, pos);
	        if(GlobalMoveData.DEBUG)   Console.WriteLine("ws: {0}",ws);
	        if(ws!=null && (ws=="." || ((int)ws[0]) > 96))
		        GlobalMoveData.valid_white_moves[GlobalMoveData.num_valid_white_moves++] = move_knight_westsouth(board, pos);
		
	        // check westnorth
	        string wn = whats_knight_westnorth(board, pos);
	        if(GlobalMoveData.DEBUG)   Console.WriteLine("wn: {0}",wn);
	        if(wn!=null && (wn=="." || ((int)wn[0]) > 96))
		        GlobalMoveData.valid_white_moves[GlobalMoveData.num_valid_white_moves++] = move_knight_westnorth(board, pos);		
        }

        static void valid_white_pawn_moves(string board, int pos)
        {
	        // check north
	        string n = whats_north(board, pos);
	        if(GlobalMoveData.DEBUG)   Console.WriteLine("n: {0}",n);
	        if(n!=null && n==".")
		        GlobalMoveData.valid_white_moves[GlobalMoveData.num_valid_white_moves++] = move_pawn_north(board, pos);
	
	        // check northwest
	        string nw = whats_northwest(board, pos);
	        if(GlobalMoveData.DEBUG)   Console.WriteLine("nw: {0}",nw);
	        if(nw!=null && ((int)nw[0]) > 96)
		        GlobalMoveData.valid_white_moves[GlobalMoveData.num_valid_white_moves++] = move_pawn_northwest(board, pos);
	
	        // check northeast
	        string ne = whats_northeast(board, pos);
	        if(GlobalMoveData.DEBUG)   Console.WriteLine("ne: {0}",ne);
	        if(ne!=null && ((int)ne[0]) > 96)
		        GlobalMoveData.valid_white_moves[GlobalMoveData.num_valid_white_moves++] = move_pawn_northeast(board, pos);
        }


        static void valid_black_king_moves(string board, int pos)
        {
	        // check north
	        string n = whats_north(board, pos);
	        if(GlobalMoveData.DEBUG)   Console.WriteLine("n: {0}",n);
	        if(n!=null && ((int)n[0]) < 96)
		        GlobalMoveData.valid_black_moves[GlobalMoveData.num_valid_black_moves++] = move_north(board, pos);
	
	        // check west
	        string w = whats_west(board, pos);
	        if(GlobalMoveData.DEBUG)   Console.WriteLine("w: {0}",w);
	        if(w!=null && ((int)w[0]) < 96)
		        GlobalMoveData.valid_black_moves[GlobalMoveData.num_valid_black_moves++] = move_west(board, pos);

	        // check south
	        string s = whats_south(board, pos);
	        if(GlobalMoveData.DEBUG)   Console.WriteLine("s: {0}",s);
	        if(s!=null && ((int)s[0]) < 96)
		        GlobalMoveData.valid_black_moves[GlobalMoveData.num_valid_black_moves++] = move_south(board, pos);

	        // check east
	        string e = whats_east(board, pos);
	        if(GlobalMoveData.DEBUG)   Console.WriteLine("e: {0}",e);
	        if(e!=null && ((int)e[0]) < 96)
		        GlobalMoveData.valid_black_moves[GlobalMoveData.num_valid_black_moves++] = move_east(board, pos);
	
	        // check southeast
	        string se = whats_southeast(board, pos);
	        if(GlobalMoveData.DEBUG)   Console.WriteLine("se: {0}",se);
	        if(se!=null && ((int)se[0]) < 96)
		        GlobalMoveData.valid_black_moves[GlobalMoveData.num_valid_black_moves++] = move_southeast(board, pos);
	
	        // check southwest
	        string sw = whats_southwest(board, pos);
	        if(GlobalMoveData.DEBUG)   Console.WriteLine("sw: {0}",sw);
	        if(sw!=null && ((int)sw[0]) < 96)
		        GlobalMoveData.valid_black_moves[GlobalMoveData.num_valid_black_moves++] = move_southwest(board, pos);
	
	        // check northwest
	        string nw = whats_northwest(board, pos);
	        if(GlobalMoveData.DEBUG)   Console.WriteLine("nw: {0}",nw);
	        if(nw!=null && ((int)nw[0]) < 96)
		        GlobalMoveData.valid_black_moves[GlobalMoveData.num_valid_black_moves++] = move_northwest(board, pos);
	
	        // check northeast
	        string ne = whats_northeast(board, pos);
	        if(GlobalMoveData.DEBUG)   Console.WriteLine("ne: {0}",ne);
	        if(ne!=null && ((int)ne[0]) < 96)
		        GlobalMoveData.valid_black_moves[GlobalMoveData.num_valid_black_moves++] = move_northeast(board, pos);
        }

        static void valid_black_queen_moves(string board, int pos)
        {
	        string orig_board = board;
	        int orig_pos = pos;
	
	        // check north
	        while(true)
	        {
		        string n = whats_north(board, pos);
		        if(GlobalMoveData.DEBUG)   Console.WriteLine("n: {0}",n);
		        if(n!=null && ((int)n[0]) < 96)
		        {
			        board = move_north(board, pos);
			        GlobalMoveData.valid_black_moves[GlobalMoveData.num_valid_black_moves++] = board;
			        if(n!=".") break;
		        }
		        else
			        break;
		        pos -= 5;
	        }
	
	        // check west
	        board = orig_board;
	        pos = orig_pos;
	        while(true)
	        {
		        string w = whats_west(board, pos);
		        if(GlobalMoveData.DEBUG)   Console.WriteLine("w: {0}",w);
		        if(w!=null && ((int)w[0]) < 96)
		        {
			        board = move_west(board, pos);
			        GlobalMoveData.valid_black_moves[GlobalMoveData.num_valid_black_moves++] = board;
			        if(w!=".") break;
		        }
		        else
			        break;
		        pos--;
	        }
	
	        // check south
	        board = orig_board;
	        pos = orig_pos;
	        while(true)
	        {
		        string s = whats_south(board, pos);
		        if(GlobalMoveData.DEBUG)   Console.WriteLine("s: {0}",s);
		        if(s!=null && ((int)s[0]) < 96)
		        {
			        board = move_south(board, pos);
			        GlobalMoveData.valid_black_moves[GlobalMoveData.num_valid_black_moves++] = board;
			        if(s!=".") break;
		        }
		        else
			        break;
		        pos += 5;
	        }
	
	
	        // check east
	        board = orig_board;
	        pos = orig_pos;
	        while(true)
	        {
		        string e = whats_east(board, pos);
		        if(GlobalMoveData.DEBUG)   Console.WriteLine("e: {0}",e);
		        if(e!=null && ((int)e[0]) < 96)
		        {
			        board = move_east(board, pos);
			        GlobalMoveData.valid_black_moves[GlobalMoveData.num_valid_black_moves++] = board;
			        if(e!=".") break;
		        }
		        else
			        break;
		        pos++;
	        }
	
	        // check southeast
	        board = orig_board;
	        pos = orig_pos;
	        while(true)
	        {
		        string se = whats_southeast(board, pos);
		        if(GlobalMoveData.DEBUG)   Console.WriteLine("se: {0}",se);
		        if(se!=null && ((int)se[0]) < 96)
		        {
			        board = move_southeast(board, pos);
			        GlobalMoveData.valid_black_moves[GlobalMoveData.num_valid_black_moves++] = board;
			        if(se!=".") break;
		        }
		        else
			        break;
		        pos += 6;
	        }
	
	        // check southwest
	        board = orig_board;
	        pos = orig_pos;
	        while(true)
	        {
		        string sw = whats_southwest(board, pos);
		        if(GlobalMoveData.DEBUG)   Console.WriteLine("sw: {0}",sw);
		        if(sw!=null && ((int)sw[0]) < 96)
		        {
			        board = move_southwest(board, pos);
			        GlobalMoveData.valid_black_moves[GlobalMoveData.num_valid_black_moves++] = board;
			        if(sw!=".") break;
		        }
		        else
			        break;
		        pos += 4;
	        }
	
	
	        // check northwest
	        board = orig_board;
	        pos = orig_pos;
	        while(true)
	        {
		        string nw = whats_northwest(board, pos);
		        if(GlobalMoveData.DEBUG)   Console.WriteLine("nw: {0}",nw);
		        if(nw!=null && ((int)nw[0]) < 96)
		        {
			        board = move_northwest(board, pos);
			        GlobalMoveData.valid_black_moves[GlobalMoveData.num_valid_black_moves++] = board;
			        if(nw!=".") break;
		        }
		        else
			        break;
		        pos -= 6;	
	        }
	
	        // check northeast
	        board = orig_board;
	        pos = orig_pos;
	        while(true)
	        {
		        string ne = whats_northeast(board, pos);
		        if(GlobalMoveData.DEBUG)   Console.WriteLine("ne: {0}",ne);
		        if(ne!=null && ((int)ne[0]) < 96)
		        {
			        board = move_northeast(board, pos);
			        GlobalMoveData.valid_black_moves[GlobalMoveData.num_valid_black_moves++] = board;
			        if(ne!=".") break;
		        }
		        else
			        break;
		        pos -= 4;
	        }
        }

        static void valid_black_rook_moves(string board, int pos)
        {

	
	        string orig_board = board;
	        int orig_pos = pos;
	
	        // check north
	        while(true)
	        {
		        string n = whats_north(board, pos);
		        if(GlobalMoveData.DEBUG)   Console.WriteLine("n: {0}",n);
		        if(n!=null && ((int)n[0]) < 96)
		        {
			        board = move_north(board, pos);
			        GlobalMoveData.valid_black_moves[GlobalMoveData.num_valid_black_moves++] = board;
			        if(n!=".") break;
		        }
		        else
			        break;
		        pos -= 5;
	        }
	
	        // check west
	        board = orig_board;
	        pos = orig_pos;
	        while(true)
	        {
		        string w = whats_west(board, pos);
		        if(GlobalMoveData.DEBUG)   Console.WriteLine("w: {0}",w);
		        if(w!=null && ((int)w[0]) < 96)
		        {
			        board = move_west(board, pos);
			        GlobalMoveData.valid_black_moves[GlobalMoveData.num_valid_black_moves++] = board;
			        if(w!=".") break;
		        }
		        else
			        break;
		        pos--;
	        }
	
	        // check south
	        board = orig_board;
	        pos = orig_pos;
	        while(true)
	        {
		        string s = whats_south(board, pos);
		        if(GlobalMoveData.DEBUG)   Console.WriteLine("s: {0}",s);
		        if(s!=null && ((int)s[0]) < 96)
		        {
			        board = move_south(board, pos);
			        GlobalMoveData.valid_black_moves[GlobalMoveData.num_valid_black_moves++] = board;
			        if(s!=".") break;
		        }
		        else
			        break;
		        pos += 5;
	        }
	
	        // check east
	        board = orig_board;
	        pos = orig_pos;
	        while(true)
	        {
		        string e = whats_east(board, pos);
		        if(GlobalMoveData.DEBUG)   Console.WriteLine("e: {0}",e);
		        if(e!=null && ((int)e[0]) < 96)
		        {
			        board = move_east(board, pos);
			        GlobalMoveData.valid_black_moves[GlobalMoveData.num_valid_black_moves++] = board;
			        if(e!=".") break;
		        }
		        else
			        break;
		        pos++;
	        }
        }

        static void valid_black_bishop_moves(string board, int pos)
        {
	        string orig_board = board;
	        int orig_pos = pos;
	
	        // check north
	        string n = whats_north(board, pos);
	        if(GlobalMoveData.DEBUG)   Console.WriteLine("n: {0}",n);
	        if(n!=null && n==".")
		        GlobalMoveData.valid_black_moves[GlobalMoveData.num_valid_black_moves++] = move_north(board, pos);
	
	        // check west
	        string w = whats_west(board, pos);
	        if(GlobalMoveData.DEBUG)   Console.WriteLine("w: {0}",w);
	        if(w!=null && w==".")
		        GlobalMoveData.valid_black_moves[GlobalMoveData.num_valid_black_moves++] = move_west(board, pos);

	        // check south
	        string s = whats_south(board, pos);
	        if(GlobalMoveData.DEBUG)   Console.WriteLine("s: {0}",s);
	        if(s!=null && s==".")
		        GlobalMoveData.valid_black_moves[GlobalMoveData.num_valid_black_moves++] = move_south(board, pos);

	        // check east
	        string e = whats_east(board, pos);
	        if(GlobalMoveData.DEBUG)   Console.WriteLine("e: {0}",e);
	        if(e!=null && e==".")
		        GlobalMoveData.valid_black_moves[GlobalMoveData.num_valid_black_moves++] = move_east(board, pos);
	
	        // check southeast
	        board = orig_board;
	        pos = orig_pos;
	        while(true)
	        {
		        string se = whats_southeast(board, pos);
		        if(GlobalMoveData.DEBUG)   Console.WriteLine("se: {0}",se);
                if (se != null && ((int)se[0]) < 96)
		        {
			        board = move_southeast(board, pos);
			        GlobalMoveData.valid_black_moves[GlobalMoveData.num_valid_black_moves++] = board;
			        if(se!=".") break;
		        }
		        else
			        break;
		        pos += 6;
	        }
	
	        // check southwest
	        board = orig_board;
	        pos = orig_pos;
	        while(true)
	        {
		        string sw = whats_southwest(board, pos);
		        if(GlobalMoveData.DEBUG)   Console.WriteLine("sw: {0}",sw);
                if (sw != null && ((int)sw[0]) < 96)
		        {
			        board = move_southwest(board, pos);
			        GlobalMoveData.valid_black_moves[GlobalMoveData.num_valid_black_moves++] = board;
			        if(sw!=".") break;
		        }
		        else
			        break;
		        pos += 4;
	        }
	
	        // check northwest
	        board = orig_board;
	        pos = orig_pos;
	        while(true)
	        {
		        string nw = whats_northwest(board, pos);
		        if(GlobalMoveData.DEBUG)   Console.WriteLine("nw: {0}",nw);
                if (nw != null && ((int)nw[0]) < 96)
		        {
			        board = move_northwest(board, pos);
			        GlobalMoveData.valid_black_moves[GlobalMoveData.num_valid_black_moves++] = board;
			        if(nw!=".") break;
		        }
		        else
			        break;
		        pos -= 6;	
	        }
	
	        // check northeast
	        board = orig_board;
	        pos = orig_pos;
	        while(true)
	        {
		        string ne = whats_northeast(board, pos);
		        if(GlobalMoveData.DEBUG)   Console.WriteLine("ne: {0}",ne);
		        if (ne!=null && ((int)ne[0]) < 96)
		        {
			        board = move_northeast(board, pos);
			        GlobalMoveData.valid_black_moves[GlobalMoveData.num_valid_black_moves++] = board;
			        if(ne!=".") break;
		        }
		        else
			        break;
		        pos -= 4;
	        }
        }

        static void valid_black_knight_moves(string board, int pos)
        {
	        // check northwest
	        string nw = whats_knight_northwest(board, pos);
	        if(GlobalMoveData.DEBUG)   Console.WriteLine("nw: {0}",nw);
	        if(nw!=null && ((int)nw[0]) < 96)
		        GlobalMoveData.valid_black_moves[GlobalMoveData.num_valid_black_moves++] = move_knight_northwest(board, pos);
	
	        // check northeast
	        string ne = whats_knight_northeast(board, pos);
	        if(GlobalMoveData.DEBUG)   Console.WriteLine("ne: {0}",ne);
	        if(ne!=null && ((int)ne[0]) < 96)
		        GlobalMoveData.valid_black_moves[GlobalMoveData.num_valid_black_moves++] = move_knight_northeast(board, pos);
		
	        // check eastnorth
	        string en = whats_knight_eastnorth(board, pos);
	        if(GlobalMoveData.DEBUG)   Console.WriteLine("en: {0}",en);
	        if(en!=null && ((int)en[0]) < 96)
		        GlobalMoveData.valid_black_moves[GlobalMoveData.num_valid_black_moves++] = move_knight_eastnorth(board, pos);
		
	        // check eastsouth
	        string es = whats_knight_eastsouth(board, pos);
	        if(GlobalMoveData.DEBUG)   Console.WriteLine("es: {0}",es);
	        if(es!=null && ((int)es[0]) < 96)
		        GlobalMoveData.valid_black_moves[GlobalMoveData.num_valid_black_moves++] = move_knight_eastsouth(board, pos);
		
	        // check southeast
	        string se = whats_knight_southeast(board, pos);
	        if(GlobalMoveData.DEBUG)   Console.WriteLine("se: {0}",se);
	        if(se!=null && ((int)se[0]) < 96)
		        GlobalMoveData.valid_black_moves[GlobalMoveData.num_valid_black_moves++] = move_knight_southeast(board, pos);
		
	        // check southwest
	        string sw = whats_knight_southwest(board, pos);
	        if(GlobalMoveData.DEBUG)   Console.WriteLine("sw: {0}",sw);
	        if(sw!=null && ((int)sw[0]) < 96)
		        GlobalMoveData.valid_black_moves[GlobalMoveData.num_valid_black_moves++] = move_knight_southwest(board, pos);
		
	        // check westsouth
	        string ws = whats_knight_westsouth(board, pos);
	        if(GlobalMoveData.DEBUG)   Console.WriteLine("ws: {0}",ws);
	        if(ws!=null && ((int)ws[0]) < 96)
		        GlobalMoveData.valid_black_moves[GlobalMoveData.num_valid_black_moves++] = move_knight_westsouth(board, pos);
		
	        // check westnorth
	        string wn = whats_knight_westnorth(board, pos);
	        if(GlobalMoveData.DEBUG)   Console.WriteLine("wn: {0}",wn);
	        if(wn!=null && ((int)wn[0]) < 96)
		        GlobalMoveData.valid_black_moves[GlobalMoveData.num_valid_black_moves++] = move_knight_westnorth(board, pos);		
        }

        static void valid_black_pawn_moves(string board, int pos)
        {
	        // check south
	        string s = whats_south(board, pos);
	        if(GlobalMoveData.DEBUG)   Console.WriteLine("s: {0}",s);
	        if(s!=null && s==".")
		        GlobalMoveData.valid_black_moves[GlobalMoveData.num_valid_black_moves++] = move_pawn_south(board, pos);
	
	        // check southwest
	        string sw = whats_southwest(board, pos);
	        if(GlobalMoveData.DEBUG)   Console.WriteLine("sw: {0}",sw);
	        if(sw!=null && sw!="." && ((int)sw[0]) < 96)
		        GlobalMoveData.valid_black_moves[GlobalMoveData.num_valid_black_moves++] = move_pawn_southwest(board, pos);
	
	        // check southeast
	        string se = whats_southeast(board, pos);
	        if(GlobalMoveData.DEBUG)   Console.WriteLine("se: {0}",se);
	        if(se!=null && se!="." && ((int)se[0]) < 96)
		        GlobalMoveData.valid_black_moves[GlobalMoveData.num_valid_black_moves++] = move_pawn_southeast(board, pos);
        }


        static string whats_north(string board, int pos)
        {
	        if(pos < 6)
		        return(null);
	        else
		        return (board[pos-5].ToString());
        }

        static string whats_west(string board, int pos)
        {
	        if(pos % 5 == 0)
		        return(null);
	        else
                return (board[pos - 1].ToString());
        }

        static string whats_south(string board, int pos)
        {
	        if(pos >= 24)
		        return(null);
	        else
                return (board[pos + 5].ToString());
        }

        static string whats_east(string board, int pos)
        {
	        if(pos % 5 == 4)
		        return(null);
	        else
                return (board[pos + 1].ToString());
        }

        static string whats_northeast(string board, int pos)
        {
	        if(pos < 5 || pos % 5 == 4)
		        return(null);
	        else
                return (board[pos - 4].ToString());
        }

        static string whats_northwest(string board, int pos)
        {
	        if(pos < 5 || pos % 5 == 0)
		        return(null);
	        else
                return (board[pos - 6].ToString());
        }

        static string whats_southwest(string board, int pos)
        {
	        if(pos >= 24 || pos % 5 == 0)
		        return(null);
	        else
                return (board[pos + 4].ToString());
        }

        static string whats_southeast(string board, int pos)
        {
	        if(pos >= 25 || pos % 5 == 4)
		        return(null);
	        else
                return (board[pos + 6].ToString());
        }



        // knight moves
        static string whats_knight_northwest(string board, int pos)
        {
	        if(pos < 11 || pos % 5 == 0)
		        return(null);
	        else
                return (board[pos - 11].ToString());
        }

        static string whats_knight_northeast(string board, int pos)
        {
	        if(pos < 10 || pos % 5 == 4)
		        return(null);
	        else
                return (board[pos - 9].ToString());
        }

        static string whats_knight_eastnorth(string board, int pos)
        {
	        if(pos < 5 || pos % 5 == 3 || pos % 5 == 4)
		        return(null);
	        else
                return (board[pos - 3].ToString());
        }

        static string whats_knight_eastsouth(string board, int pos)
        {
	        if(pos > 22 || pos % 5 == 3 || pos % 5 == 4)
		        return(null);
	        else
                return (board[pos + 7].ToString());
        }

        static string whats_knight_southeast(string board, int pos)
        {
	        if(pos > 18 || pos % 5 == 4)
		        return(null);
	        else
                return (board[pos + 11].ToString());
        }

        static string whats_knight_southwest(string board, int pos)
        {
	        if(pos > 19 || pos % 5 == 0)
		        return(null);
	        else
                return (board[pos + 9].ToString());
        }

        static string whats_knight_westsouth(string board, int pos)
        {
	        if(pos > 24 || pos % 5 == 0 || pos % 5 == 1)
		        return(null);
	        else
                return (board[pos + 3].ToString());
        }

        static string whats_knight_westnorth(string board, int pos)
        {
	        if(pos < 7 || pos % 5 == 0 || pos % 5 == 1)
		        return(null);
	        else
                return (board[pos - 7].ToString());
        }



        // standard piece moves
        static string move_north(string board, int pos)
        {
            StringBuilder new_board = new System.Text.StringBuilder(board);
            new_board[pos - 5] = board[pos];
            new_board[pos] = '.';
 	        return(new_board.ToString());
        }

        static string move_east(string board, int pos)
        {
            StringBuilder new_board = new System.Text.StringBuilder(board);
	        new_board[pos+1] = board[pos];
	        new_board[pos] = '.';
	        return(new_board.ToString());
        }

        static string move_west(string board, int pos)
        {
            StringBuilder new_board = new System.Text.StringBuilder(board);
	        new_board[pos-1] = board[pos];
	        new_board[pos] = '.';
	        return(new_board.ToString());
        }

        static string move_south(string board, int pos)
        {
            StringBuilder new_board = new System.Text.StringBuilder(board); 
            new_board[pos + 5] = board[pos];
	        new_board[pos] = '.';
	        return(new_board.ToString());
        }

        static string move_northwest(string board, int pos)
        {
            StringBuilder new_board = new System.Text.StringBuilder(board); 
            new_board[pos - 6] = board[pos];
	        new_board[pos] = '.';
	        return(new_board.ToString());
        }

        static string move_northeast(string board, int pos)
        {
            StringBuilder new_board = new System.Text.StringBuilder(board); 
            new_board[pos - 4] = board[pos];
	        new_board[pos] = '.';
	        return(new_board.ToString());
        }

        static string move_southwest(string board, int pos)
        {
            StringBuilder new_board = new System.Text.StringBuilder(board); 
            new_board[pos + 4] = board[pos];
	        new_board[pos] = '.';
	        return(new_board.ToString());
        }

        static string move_southeast(string board, int pos)
        {
            StringBuilder new_board = new System.Text.StringBuilder(board); 
            new_board[pos + 6] = board[pos];
	        new_board[pos] = '.';
	        return(new_board.ToString());
        }


        // knight moves
        static string move_knight_northwest(string board, int pos)
        {
            StringBuilder new_board = new System.Text.StringBuilder(board); 
            new_board[pos - 11] = board[pos];
	        new_board[pos] = '.';
	        return(new_board.ToString());
        }

        static string move_knight_northeast(string board, int pos)
        {
            StringBuilder new_board = new System.Text.StringBuilder(board); 
            new_board[pos - 9] = board[pos];
	        new_board[pos] = '.';
	        return(new_board.ToString());
        }

        static string move_knight_eastnorth(string board, int pos)
        {
            StringBuilder new_board = new System.Text.StringBuilder(board); 
            new_board[pos - 3] = board[pos];
	        new_board[pos] = '.';
	        return(new_board.ToString());
        }

        static string move_knight_eastsouth(string board, int pos)
        {
            StringBuilder new_board = new System.Text.StringBuilder(board); 
            new_board[pos + 7] = board[pos];
	        new_board[pos] = '.';
	        return(new_board.ToString());
        }

        static string move_knight_southeast(string board, int pos)
        {
            StringBuilder new_board = new System.Text.StringBuilder(board); 
            new_board[pos + 11] = board[pos];
	        new_board[pos] = '.';
	        return(new_board.ToString());
        }

        static string move_knight_southwest(string board, int pos)
        {
            StringBuilder new_board = new System.Text.StringBuilder(board); 
            new_board[pos + 9] = board[pos];
	        new_board[pos] = '.';
	        return(new_board.ToString());
        }

        static string move_knight_westsouth(string board, int pos)
        {
            StringBuilder new_board = new System.Text.StringBuilder(board); 
            new_board[pos + 3] = board[pos];
	        new_board[pos] = '.';
	        return(new_board.ToString());
        }

        static string move_knight_westnorth(string board, int pos)
        {
            StringBuilder new_board = new System.Text.StringBuilder(board); 
            new_board[pos - 7] = board[pos];
	        new_board[pos] = '.';
	        return(new_board.ToString());
        }

        // pawn moves
        static string move_pawn_north(string board, int pos)
        {
            StringBuilder new_board = new System.Text.StringBuilder(board);
	        if(pos < 10)
		        new_board[pos-5] = 'Q';
	        else
		        new_board[pos-5] = board[pos];
	        new_board[pos] = '.';
	        return(new_board.ToString());
        }

        static string move_pawn_northwest(string board, int pos)
        {
            StringBuilder new_board = new System.Text.StringBuilder(board); 
            if (pos < 10)
		        new_board[pos-6] = 'Q';
	        else
		        new_board[pos-6] = board[pos];
	        new_board[pos] = '.';
	        return(new_board.ToString());
        }

        static string move_pawn_northeast(string board, int pos)
        {
            StringBuilder new_board = new System.Text.StringBuilder(board); 
            if (pos < 10)
		        new_board[pos-4] = 'Q';
	        else
		        new_board[pos-4] = board[pos];
	        new_board[pos] = '.';
	        return(new_board.ToString());
        }

        static string move_pawn_south(string board, int pos)
        {

            StringBuilder new_board = new System.Text.StringBuilder(board); 
            if (pos > 19)
                new_board[pos + 5] = 'q';
	        else
		        new_board[pos+5] = board[pos];
	        new_board[pos] = '.';
	        return(new_board.ToString());
        }

        static string move_pawn_southwest(string board, int pos)
        {
            StringBuilder new_board = new System.Text.StringBuilder(board); 
            if (pos > 19)
                new_board[pos + 4] = 'q';
	        else
		        new_board[pos+4] = board[pos];
	        new_board[pos] = '.';
	        return(new_board.ToString());
        }

        static string move_pawn_southeast(string board, int pos)
        {
            StringBuilder new_board = new System.Text.StringBuilder(board); 
            if (pos > 19)
                new_board[pos + 6] = 'q';
	        else
		        new_board[pos+6] = board[pos];
	        new_board[pos] = '.';
	        return(new_board.ToString());
        }


        // heuristics
        static string get_best_white_move()
        {
            Random random = new Random();
            int randomNumber = random.Next(0, GlobalMoveData.num_valid_white_moves-1);
            return(GlobalMoveData.valid_white_moves[randomNumber]);
            /*
	        int best_score = -999999999;
	        string best_move = "";
            int score;
	
            for(int i=0;i<GlobalMoveData.num_valid_white_moves;i++)
            {
                score = basic_score(GlobalMoveData.valid_white_moves[i]);
		        if(score > best_score)
		        {
			        best_score = score;
			        best_move = GlobalMoveData.valid_white_moves[i];
		        }
            }
	        return(best_move);
            */
        }

        static string get_best_black_move()
        {
            Random random = new Random();
            int randomNumber = random.Next(0, GlobalMoveData.num_valid_black_moves-1);
            return(GlobalMoveData.valid_black_moves[randomNumber]);
            /*
            int best_score = -999999999;
            string best_move = "";
            int score;

            for (int i = 0; i < GlobalMoveData.num_valid_black_moves; i++)
            {
                score = basic_score(GlobalMoveData.valid_black_moves[i]);
                if (score > best_score)
                {
                    best_score = score;
                    best_move = GlobalMoveData.valid_black_moves[i];
                }
            }
            return (best_move);
            */
        }

        /*
        score as in standard chess, with 
        100 per pawn,
        300 for its Bishop or Knight, 
        500 for its Rook, and 
        900 for its Queen. 
        1800 for its King
        Take the difference between the two sides to get the score.
        */
        static int basic_score(string board)
        {
	        int white_score = 0;
	        int black_score = 0;
	
	        for(int i=0;i<board.Length;i++)
	        {
		        switch(board[i])
		        {
			        case 'k': black_score += 1800; break;
			        case 'q': black_score += 900; break;
			        case 'b': black_score += 300; break;
			        case 'n': black_score += 300; break;
			        case 'r': black_score += 500; break;
			        case 'p': black_score += 100; break;
			        case 'K': white_score += 1800; break;
			        case 'Q': white_score += 900; break;
			        case 'B': white_score += 300; break;
			        case 'N': white_score += 300; break;
			        case 'R': white_score += 500; break;
			        case 'P': white_score += 100; break;
		        }
	        }

            //print_board(board);
            //Console.WriteLine("score: {0}", white_score - black_score);
	
	        return(white_score - black_score);
        }


       

        static string best_negamax_move(string board, int color, int ms)
        {
            int depth = 1;
            System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
            sw.Start();
            string[] options = new string[1000];
            int num_options = 0;
            if(color == 1)
            {
                Array.Clear(GlobalMoveData.valid_white_moves, 0, GlobalMoveData.num_valid_white_moves);
                GlobalMoveData.num_valid_white_moves = 0;
                get_valid_white_moves(board);
                GlobalMoveData.valid_white_moves.CopyTo(options,0);
                num_options = GlobalMoveData.num_valid_white_moves;
            }
            else
            {
                Array.Clear(GlobalMoveData.valid_black_moves, 0, GlobalMoveData.num_valid_black_moves);
                GlobalMoveData.num_valid_black_moves = 0;
                get_valid_black_moves(board);
                GlobalMoveData.valid_black_moves.CopyTo(options,0);
                num_options = GlobalMoveData.num_valid_black_moves;
            }

            int current_value = 0;
            int best_value = -999999999;
            int depth_best_value = -999999999;
            string best_move = "";
            string depth_best_move = "";
            while (true)
            {
                //Console.WriteLine("ms: {0} of {1}", sw.ElapsedMilliseconds,ms);
                //depth_best_value = -999999999;

                for(int i=0;i<num_options;i++)
                {
                    current_value = -negamax(options[i],depth-1,-color);

                    //Console.WriteLine("move: {0}", current_value);
                    //print_board(options[i]);

                    if(current_value > depth_best_value)
                    {
                        depth_best_value = current_value;
                        depth_best_move = options[i];
                        
                    }
                    if (sw.ElapsedMilliseconds > ms)
                        break;
                }
                if (sw.ElapsedMilliseconds > ms)
                    break;

                best_move = depth_best_move;
                best_value = depth_best_value;

                //Console.WriteLine("best move/value for depth: {0} = {1}", depth,best_value);
                //print_board(best_move);

                depth++;
            }
            return(best_move);
        }


        /*
       // negamax pseudocode code implementation with alpha-beta pruning, from wikipedia (http://wiki.cs.pdx.edu/cs542-spring2013/hw/hw-2)
       function negamax(node, depth, α, β, color)
           if node is a terminal node or depth = 0
               return color * the heuristic value of node
           else
               foreach child of node
                   val := -negamax(child, depth-1, -β, -α, -color)
                   if val≥β
                       return val
                   if val>α
                       α:=val
               return α

       */
        static int negamax(string node,int depth,int color)
        {
            int value = 0;
            int best_value = -999999999;
            int score = 0;
	        string[] children = get_node_children(node,color);
	        if(children[0]==null || depth == 0)
	        {   
                score = color * basic_score(node);
                //Console.WriteLine("score.... {0}", score);

                return (basic_score(node));
	        }
	        else
	        {
		        for(int i=0;i<children.Length;i++)
		        {
                    if (children[i] == null)
                        break;

			        value = -negamax(children[i], depth-1, -color);
                    
                    //Console.WriteLine("value: {0}", value);
                    //print_board(children[i]);

                    if (value > best_value)
                    {
                        best_value = value;
                    }
		        }
		        return(best_value);
	        }
	
        }

        static string[] get_node_children(string node,int color)
        {
            if(color == 1)
            {
                Array.Clear(GlobalMoveData.valid_white_moves, 0, GlobalMoveData.num_valid_white_moves);
                GlobalMoveData.num_valid_white_moves = 0;
                get_valid_white_moves(node);
                return(GlobalMoveData.valid_white_moves);
            }
            else
            {
                Array.Clear(GlobalMoveData.valid_black_moves, 0, GlobalMoveData.num_valid_black_moves);
                GlobalMoveData.num_valid_black_moves = 0;
                get_valid_black_moves(node);
                return(GlobalMoveData.valid_black_moves);
            }
        }

        // utility functions
        static void print_board(string board)
        {
	        for(int i=0;i<6;i++)
	        {
		        for(int j=0;j<5;j++)
		        {
			        Console.Write(board[i*5+j]);
		        }
		        Console.Write("\n");
	        }
            Console.Write("\n");
        }

        static string reset_board()
        {
	        string board = "kqbnrppppp..........PPPPPRNBQK";
	        return(board);
        }

        static int game_over(string board,int move_count)
        {
            if (move_count > 40)
                return 3;

	        bool white_ok = false;
	        bool black_ok = false;
	
	        for(int i=0;i<board.Length;i++)
	        {
		        if(board[i]=='K')
		        {
			        if(black_ok) return 0;
			        white_ok = true;
		        }
		        else if(board[i]=='k')
		        {
			        if(white_ok) return 0;
			        black_ok = true;
		        }
	        }

            if (black_ok) return 1;
            else return 2;
        }


        // required move functions
        static string humanMove(string human_move,string board,string turn)
        {
            string new_board = move(human_move, board);
            if (turn == "W")
            {
                for (int i = 0; i < GlobalMoveData.num_valid_white_moves; i++)
                {
                    if(GlobalMoveData.valid_white_moves[i].CompareTo(new_board) == 0)
                        return (new_board.ToString());
                }

                // invalid move
                Console.WriteLine("Invalid move... please try again.");
                return (board);
            }
            else
            {
                for (int i = 0; i < GlobalMoveData.num_valid_black_moves; i++)
                {
                    if (GlobalMoveData.valid_black_moves[i].CompareTo(new_board) == 0)
                        return (new_board.ToString());
                }

                // invalid move
                Console.WriteLine("Invalid move... please try again.");
                return (board);
            }
        }

        static string move(string human_move, string board)
        {
            // split human move into something usable
            int i = 0;
            int j = 0;
            int k = 0;
            int l = 0;

            switch (human_move[0])
            {
                case 'a': i = 0; break;
                case 'b': i = 1; break;
                case 'c': i = 2; break;
                case 'd': i = 3; break;
                case 'e': i = 4; break;
            }

            j = ((int)human_move[1]);

            switch (human_move[3])
            {
                case 'a': k = 0; break;
                case 'b': k = 1; break;
                case 'c': k = 2; break;
                case 'd': k = 3; break;
                case 'e': k = 4; break;
            }

            l = ((int)human_move[4]);

            StringBuilder new_board = new System.Text.StringBuilder(board);
            new_board[k*5+l] = board[i*5+k];
            new_board[i*5+k] = '.';
            return (new_board.ToString());
        }

    }
}
